// https://www.luogu.com.cn/problem/P5960
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int inf = 0x3f3f3f3f;
const ll infLL = 0x3f3f3f3f3f3f3f3fLL;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
#define MAX_SIZE 5005
#define MAXN 5005

int n, m, esiz;
struct Node {
    int to, w;
    Node *nex;
} edg[MAX_SIZE << 1], *head[MAXN];

inline void add(int l, int r, int w) { edg[++esiz] = {r, w, head[l]}, head[l] = edg + esiz; }

bool visit[MAXN];
int dis[MAXN], cnt[MAXN];
bool SPFA(int start = 1) {
    // memset(visit, 0, sizeof(visit));
    // memset(cnt, 0, sizeof(cnt));
    memset(dis, inf, sizeof(dis));
    queue<int> qe;
    qe.push(start), visit[start] = 1, dis[start] = 0;
    while (!qe.empty()) {
        int now = qe.front();
        qe.pop(), visit[now] = 0;
        for (Node *p = head[now]; p; p = p->nex) {
            if (dis[p->to] > dis[now] + p->w) {
                dis[p->to] = dis[now] + p->w;
                if (!visit[p->to]) {
                    qe.push(p->to), visit[p->to] = 1;
                    if (++cnt[p->to] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int l, r, w;
        scanf("%d%d%d", &l, &r, &w);
        add(r, l, w);
    }
    rf(i, n)
        add(n + 1, i, 0);
    if (SPFA(n + 1) == 0)
        puts("NO");
    else
        rf(i, n)
            printf("%d ", dis[i]);
}
